
//1293.网格中的最短路径
struct Step
{
    int _x,_y;  //该位置的坐标
    int _rest;  //到达该位置时剩余可以消除障碍物的个数
    Step(int x,int y,int rest):_x(x),_y(y),_rest(rest){}
};

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        //使用BFS,只不过在向外进行扩展的时候,对每个位置记录以下已经移除的障碍物的个数
        int n=grid.size(),m=grid[0].size(),step=0;
        if(n==1&&m==1) return 0;
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};
        k=min(k,m+n-3);   //做多会移除m+n-3个障碍物,所以可以对此处进行剪枝

        vector<vector<int>> vist(n,vector<int>(m,-1));  //记录到达每个位置剩余移除障碍物的次数
        vist[0][0]=k;
        queue<Step> q;
        q.push(Step(0,0,k)); 
        while(!q.empty())
        {
            int _size=q.size();
            for(int i=0;i<_size;i++)
            {
                int x=q.front()._x,y=q.front()._y;
                int rest=q.front()._rest;
                if(x==n-1&&y==m-1) return step;
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k],tmp=rest;
                    if(a>=0&&a<n&&b>=0&&b<m)
                    {
                        if(grid[a][b]) tmp--;   //是障碍物
                        if(tmp<0) continue;      //依次次数超过限制
                        if(vist[a][b]==-1||tmp>vist[a][b])   //没有到达的位置或已经达到了但是剩余次数较少
                        {
                            q.push(Step(a,b,tmp));
                            vist[a][b]=tmp;
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};